package array.hard;

import java.time.LocalDateTime;

/**
 * 接雨水
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 *
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 */
public class TrappingRainWater_42 {
    public int trap(int[] height) {
        //计算找到最高的柱子
        int mostHeightIndex = 0;
        for (int i = 1; i < height.length; i++) {
            if (height[mostHeightIndex] < height[i])
                mostHeightIndex = i;
        }

        int countWater = 0;

        //计算最高柱子左边的雨水
        int leftI = 0;
        int leftJ = 0;
        while(leftJ <= mostHeightIndex) {
            if (height[leftI] < height[leftJ]) {
                int offset = 1;
                //由低遇到高的则运算
                while((leftI + offset) < leftJ) {
                    countWater += height[leftI] - height[leftI + offset];
                    offset++;
                }
                leftI = leftJ;
            }else{
                leftJ++;
            }
        }

        int rightI = mostHeightIndex;
        int rightJ = height.length - 1;
        //计算最高柱子右边的雨水
        while(rightI < rightJ) {
            if (height[rightJ] < height[rightJ - 1]) {
                rightJ--;
            } else {
                int offset = 1;
                //由高遇到低的进行运算
                while(height[rightJ] > height[rightJ - offset]) {
                    countWater += height[rightJ] - height[rightJ - offset];
                    offset++;
                }
                rightJ = rightJ - offset;
            }
        }

        return countWater;
    }

    public static void main(String[] args) {
        TrappingRainWater_42 tr = new TrappingRainWater_42();
        System.out.println(tr.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }
}
